package day10;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <a href="https://leetcode.cn/problems/longest-common-prefix/">14.最长公共前缀</a>
 * @author admin
 */
public class Answer {

    public static void main(String[] args) {
        String[] strs = new String[]{"aaa","aa","aaa"};
        Answer answer = new Answer();
        String s = answer.longestCommonPrefix(strs);
        System.out.println(s);
    }

    /**
     * 排序得到长度最短的字符串，依次比较
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        List<String> collect = Arrays.stream(strs).sorted().collect(Collectors.toList());
        String begin = collect.get(0);
        String finalString = "";
        for (int i = 0; i <= begin.length(); i++) {
            String word = begin.substring(0, i);
            boolean last = false;
            for (int j = 1; j < strs.length; j++) {
                last = collect.get(j).startsWith(word);
            }
            if (last) {
                finalString = word;
            }
        }
        return finalString;
    }

    /**
     * 解题思路：把两个字符串相同的拿出来和后续的比较
     * @param strs
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            prefix = getPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;

    }

    private String getPrefix(String s1, String s2) {
        int min = Math.min(s1.length(), s2.length());
        int index = 0;

        while (index < min && s1.charAt(index) == s2.charAt(index)) {
            index++;
        }
        return s1.substring(0, index);
    }
}
